package demo3;
import java.util.*;
public class Solution {
    //1.零钱兑换(回溯)
    private List<List<Integer>> list = new ArrayList<>();
    private int amount;
    public int coinChange(int[] coins, int amount) {
        this.amount = amount;
        List<Integer> path = new ArrayList<>();
        dfs(coins, path, 0);
        if(list.isEmpty()) {
            return -1;
        }
        //找出长度最小的
        int min = Integer.MAX_VALUE;//最小硬币个数
        for(int i = 0; i < list.size(); i++) {
            int len = list.get(i).size();
            if(len < min) {
                min = len;
            }
        }
        return min;
    }
    private void dfs(int[] coins, List<Integer> path, int sum) {
        if(sum == amount) {
            list.add(new ArrayList<>(path));
            return;
        } else if(sum > amount) {
            return;
        }
        for(int i = 0; i < coins.length; i++) {
            if(!path.isEmpty() && path.get(path.size() - 1) < coins[i]) {
                //顺序不一样就不用看了
                continue;
            }
            path.add(coins[i]);
            dfs(coins, path, sum + coins[i]);
            path.remove(path.size() - 1);
        }
    }
    //1.零钱兑换(回溯空间优化)
//    private int ret = Integer.MAX_VALUE;
//    public int coinChange(int[] coins, int amount) {
//        dfs(coins, amount, 0);
//        if(ret == Integer.MAX_VALUE) {
//            return -1;
//        }
//        return ret;
//    }
//    private void dfs(int[] coins, int amount, int count) {
//        if(amount == 0) {
//            ret = Math.min(ret, count);
//            return;
//        } else if(amount < 0) {
//            return;
//        }
//        for(int i = 0; i < coins.length; i++) {
//            dfs(coins, amount - coins[i], count + 1);
//        }
//    }

    //2.全排列 II
//    private List<List<Integer>> ret = new ArrayList<>();
//    public List<List<Integer>> permuteUnique(int[] nums) {
//        List<Integer> path = new ArrayList<>();
//        boolean[] used = new boolean[nums.length];
//        dfs(nums, path, used);
//        return ret;
//    }
//    private void dfs(int[] nums, List<Integer> path, boolean[] used) {
//        if(path.size() == nums.length) {
//            if(!ret.contains(path)) {
//                ret.add(new ArrayList<>(path));
//            }
//            return;
//        }
//        for(int i = 0; i < nums.length; i++) {
//            if(used[i]) {
//                continue;
//            }
//            used[i] = true;
//            path.add(nums[i]);
//            dfs(nums, path, used);
//            path.remove(path.size() - 1);
//            used[i] = false;
//        }
//    }
    //全排列 II(优化)
//    private List<List<Integer>> ret = new ArrayList<>();
//    public List<List<Integer>> permuteUnique(int[] nums) {
//        List<Integer> path = new ArrayList<>();
//        boolean[] used = new boolean[nums.length];
//        Arrays.sort(nums);
//        dfs(nums, path, used);
//        return ret;
//    }
//    private void dfs(int[] nums, List<Integer> path, boolean[] used) {
//        if(path.size() == nums.length) {
//            ret.add(new ArrayList<>(path));
//            return;
//        }
//        for(int i = 0; i < nums.length; i++) {
//            if(used[i]) {
//                continue;
//            }
//            //去重
//            //used[i - 1]说明判断前一个元素是否用过了（前提是有序）
//            if(i > 0 && nums[i] == nums[i - 1] && used[i - 1]) {
//                continue;
//            }
//            used[i] = true;
//            path.add(nums[i]);
//            dfs(nums, path, used);
//            path.remove(path.size() - 1);
//            used[i] = false;
//        }
//    }
    //3.组合(回溯)
//    private List<List<Integer>> ret = new ArrayList<>();
//    public List<List<Integer>> combine(int n, int k) {
//        List<Integer> path = new ArrayList<>();
//        dfs(n, k, path);
//        return ret;
//    }
//    private void dfs(int n, int k, List<Integer> path) {
//        if(path.size() == k) {
//            ret.add(new ArrayList<>(path));
//            return;
//        }
//        for(int i = 1; i <= n; i++) {
//            if(path.contains(i)) {
//                continue;
//            }
//            if(!path.isEmpty() && path.get(path.size() - 1) > i) {
//                continue;
//            }
//            path.add(i);
//            dfs(n, k, path);
//            path.remove(path.size() - 1);
//        }
//    }
    //3.组合(优化)
//    private List<List<Integer>> ret = new ArrayList<>();
//    public List<List<Integer>> combine(int n, int k) {
//        if(n < k) {
//            return ret;
//        }
//        List<Integer> path = new ArrayList<>();
//        dfs(n, k, 1, path);
//        return ret;
//    }
//    private void dfs(int n, int k, int begin, List<Integer> path) {
//        if(path.size() == k) {
//            ret.add(new ArrayList<>(path));
//            return;
//        }
//        for(int i = begin; i <= n; i++) {
//            path.add(i);
//            dfs(n, k, i + 1, path);//i + 1是因为下一个不能重复
//            path.remove(path.size() - 1);
//        }
//    }
    //4.组合总和 II(回溯超时)
//    private List<List<Integer>> ret = new ArrayList<>();
//    private int target;
//    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
//        this.target = target;
//        List<Integer> path = new ArrayList<>();
//        Arrays.sort(candidates);
//        boolean[] used = new boolean[candidates.length];
//        dfs(candidates, 0, path, used, 0);
//        return ret;
//    }
//    private void dfs(int[] candidates, int begin, List<Integer> path, boolean[] used, int sum) {
//        if(sum == target) {
//            if(ret.contains(path)) {
//                ret.add(new ArrayList<>(path));
//            }
//            return;
//        }
//        for(int i = begin; i < candidates.length; i++) {
//            if(used[i]) {
//                continue;
//            }
//            if(!path.isEmpty() && path.get(path.size() - 1) > candidates[i]) {
//                continue;
//            }
//            path.add(candidates[i]);
//            used[i] = true;
//            dfs(candidates, i + 1, path, used, sum + candidates[i]);
//            path.remove(path.size() - 1);
//            used[i] = false;
//        }
//    }
    //4.组合总和 II(回溯剪枝)
//    private List<List<Integer>> ret = new ArrayList<>();
//    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
//        Deque<Integer> path = new ArrayDeque<>();
//        Arrays.sort(candidates);
//        dfs(candidates, path, 0, target);
//        return ret;
//    }
//    private void dfs(int[] candidates, Deque<Integer> path, int begin, int target) {
//        if(target == 0) {
//            ret.add(new ArrayList<>(path));
//            return;
//        }
//        for(int i = begin; i < candidates.length; i++) {
//            if(target - candidates[i] < 0) {//排序后，后面的越来越大，一旦出现小于0的，后面就不用看了
//                break;
//            }
//            if(i > begin && candidates[i - 1] == candidates[i]) {//排序后，就可以这样处理
//                continue;
//            }
//            path.addLast(candidates[i]);
//            dfs(candidates, path, i + 1, target - candidates[i]);
//            path.removeLast();
//        }
//    }
    //5.JZ10 斐波那契数列
//    public int Fibonacci(int n) {
//        //定义一个数组，用来保存中间状态
//        int[] dp = new int[n + 1];
//        //初始化，保证顺利递推
//        dp[0] = 0;
//        dp[1] = 1;
//        //由初始化可以得出第三项，因此i从下标2开始，通过递推公式得到第n项
//        for(int i = 2; i <= n; i++) {
//            //列出状态转移方程
//            dp[i] = dp[i - 1] + dp[i - 2];
//        }
//        //返回结果
//        return dp[n];
//    }
    public int Fibonacci(int n) {
        int fn = 0;
        int f1 = 1;//这里就是f(n-1)
        int f2 = 0;//这里就是f(n-2)
        for(int i = 2; i <= n; i++) {
            fn = f1 + f2;
            //更新状态
            f2 = f1;
            f1 = fn;
        }
        return fn;
    }
    //6.拆分词句
    public boolean wordBreak(String s, Set<String> dict) {
        //定义一个数组，用来表示每个i的状态
        boolean[] dp = new boolean[s.length() + 1];
        //初始化
        dp[0] = true;
        for(int i = 1; i <= s.length(); i++) {
            for(int j = 0; j < i; j++) {
                if(dp[j] && dict.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }
    //6.单词拆分(动态规划)
    public boolean wordBreak(String s, List<String> wordDict) {
        //f(i)表示可以拼接出前i个字符（剩下的字符需要再字典中包括即可）
        boolean[] dp = new boolean[s.length() + 1];
        //f(4) && [5, 8]能够在字典中找到
        //f(8):f(1) && [2, 8]
        //状态转移方程:f(i) = f(j) && [j + 1, i]能被找到
        //初始化
        dp[0] = true;
        for(int i = 1; i <= s.length(); i++) {
            for(int j = 0; j < i; j++) {
                if(dp[j] && wordDict.contains(s.substring(j, i))) {
                    //表示在前j个字符可以拆分的前提下，j + 1 ~ i个字符可以在字典中找到
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }
    //7.剑指 Offer II 100. 三角形中最小路径之和
    // [2],
    // [3,4],
    // [6,5,7],
    // [4,1,8,3]
//    public int minimumTotal(List<List<Integer>> triangle) {
//        int row = triangle.size();//行
//        //这里是否创建新的数组？可以不用创建的，题目中所给数组以及满足需求，我们
//        //可以直接根据题目中所给的数据继续递推下去
//        for(int i = 1; i < row; i++) {
//            for(int j = 0; j < triangle.get(i).size(); j++) {
//                if(j == 0) {//左边边界：只能有上面的一个元素得出
//                    triangle.get(i).set(j, triangle.get(i - 1).get(j) + triangle.get(i).get(j));
//                } else if(i == j) {//右边边界：只能由左上方的元素得出
//                    triangle.get(i).set(j, triangle.get(i - 1).get(j - 1) + triangle.get(i).get(j));
//                } else {//其他情况
//                    triangle.get(i).set(j, Math.min(
//                            triangle.get(i - 1).get(j), triangle.get(i - 1).get(j - 1)
//                    ) + triangle.get(i).get(j));
//                }
//            }
//        }
//        //返回最底层的最小值
//        int min = Integer.MAX_VALUE;
//        for(int i = 0; i < triangle.get(row - 1).size(); i++) {
//            min = Math.min(min, triangle.get(row - 1).get(i));
//        }
//        return min;
//    }

//    public int minimumTotal(List<List<Integer>> triangle) {
//        int row = triangle.size();//行
//        //这里是否创建新的数组？可以不用创建的，题目中所给数组以及满足需求，我们
//        //可以直接根据题目中所给的数据继续递推下去
//        for(int i = 1; i < row; i++) {
//            for(int j = 0; j <= i; j++) {
//                if(j == 0) {//左边边界：只能有上面的一个元素得出
//                    triangle.get(i).set(j, triangle.get(i - 1).get(j) + triangle.get(i).get(j));
//                } else if(i == j) {//右边边界：只能由左上方的元素得出
//                    triangle.get(i).set(j, triangle.get(i - 1).get(j - 1) + triangle.get(i).get(j));
//                } else {//其他情况
//                    triangle.get(i).set(j, Math.min(
//                            triangle.get(i - 1).get(j), triangle.get(i - 1).get(j - 1)
//                    ) + triangle.get(i).get(j));
//                }
//            }
//        }
//        //返回最底层的最小值
//        int min = Integer.MAX_VALUE;
//        for(int i = 0; i < triangle.get(row - 1).size(); i++) {
//            min = Math.min(min, triangle.get(row - 1).get(i));
//        }
//        return min;
//    }
        public int minimumTotal(List<List<Integer>> triangle) {
            //自底而上
            int row = triangle.size();
            for(int i = row - 2; i >= 0; i--) {//这里最后一行就是初始值，所以要从倒数第二行开始
                for(int j = 0; j <= i; j++) {
                    triangle.get(i).set(j, Math.min(
                            triangle.get(i + 1).get(j), triangle.get(i + 1).get(j + 1)
                    ) + triangle.get(i).get(j));
                }
            }
            return triangle.get(0).get(0);
        }
    //8.CC88 不同路径的数目(一)（动态规划）
    public int uniquePaths (int m, int n) {
        int[][] dp = new int[m][n];
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(i == 0 || j == 0) {//最左侧和最上层
                    dp[i][j] = 1;
                } else {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }
        return dp[m - 1][n - 1];
    }
    //CC86 带权值的最小路径和(动态规划)
    public int minPathSum (int[][] grid) {
        int row = grid.length;
        for(int i = 0; i < row; i++) {
            for(int j = 0; j < grid[i].length; j++) {
                if(i == 0 && j > 0) {//第一层
                    grid[i][j] = grid[i][j - 1] + grid[i][j];
                } else if(j == 0 && i > 0) {//第一列
                    grid[i][j] = grid[i - 1][j] + grid[i][j];
                } else if(i > 0 && j > 0){
                    grid[i][j] = Math.min(
                            grid[i - 1][j], grid[i][j - 1]) + grid[i][j];
                }
            }
        }
        return grid[row - 1][grid[row - 1].length - 1];
    }

    //9. 背包问题（二）（动态规划）
    public int backPackII(int m, int[] a, int[] v) {
        int n = a.length;//表示商品总个数
        int[][] dp = new int[n + 1][m + 1];
        //初始化
        for(int i = 0; i <= m; i++) {
            dp[0][i] = 0;
        }
        for(int i = 0; i <= n; i++) {
            dp[i][0] = 0;
        }
        //递推
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                if(a[i - 1] <= j) {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - a[i - 1]] + v[i - 1]);
                }else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[n][m];
    }

//    public int backPackII(int m, int[] a, int[] v) {
//        int n = a.length;//表示商品总个数
//        int[][] dp = new int[n + 1][m + 1];
//        //初始化(默认是0，就不用了)
//        // for(int i = 0; i <= m; i++) {
//        //     dp[0][i] = 0;
//        // }
//        // for(int i = 0; i <= n; i++) {
//        //     dp[i][0] = 0;
//        // }
//        //递推
//        for(int i = 1; i <= n; i++) {
//            for(int j = 1; j <= m; j++) {
//                if(a[i - 1] <= j) {
//                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - a[i - 1]] + v[i - 1]);
//                }else {
//                    dp[i][j] = dp[i - 1][j];
//                }
//            }
//        }
//        return dp[n][m];
//    }

//    public int backPackII(int m, int[] a, int[] v) {
//        int n = a.length;//表示商品总个数
//        int[] dp = new int[m + 1];
//        //递推
//        for(int i = 1; i <= n; i++) {
//            //注意这里要从后向前打印，因为这一行未更新的值就是上一行的值，而我们需要的就是
//            //上一行当前列和上一行前面某一列的值；
//            for(int j = m; j > 0; j--) {
//                if(a[i - 1] <= j) {
//                    dp[j] = Math.max(dp[j], dp[j - a[i - 1]] + v[i - 1]);
//                }
//                //else的部分也就不需要了，因为从后往前更新，未更新的值就是上一行的值
//                //也就是说，当a[i - 1]>j时，直接不用管就可以了；
//                // else {
//                //     dp[i][j] = dp[i - 1][j];
//                // }
//            }
//        }
//        return dp[m];
//    }
    //分割回文串 II(动态规划)
//    public int minCut(String s) {
//        int len = s.length();
//        if(len == 0) {
//            return 0;
//        }
//        if(judge(s, 0, len - 1)) {
//            return 0;
//        }
//        int[] dp = new int[len + 1];
//        //初始化
//        //填充可以被分割的最大次数
//        for(int i = 1; i <= len; i++) {
//            dp[i] = i - 1;
//        }
//        for(int i = 2; i <= len; i++) {
//            if(judge(s, 0, i - 1)){//若前i个字符串整体回文
//                dp[i] = 0;
//                continue;
//            }
//            for(int j = 1; j < i; j++) {
//                if(judge(s, j, i - 1)) {//注意索引
//                    dp[i] = Math.min(dp[i], dp[j] + 1);
//                }
//            }
//        }
//        return dp[len];
//    }
//    //判断回文
//    private boolean judge(String s, int start, int end) {
//        while(start < end) {
//            if(s.charAt(start) == s.charAt(end)) {
//                start++;
//                end--;
//            } else {
//                break;
//            }
//        }
//        return start < end ? false : true;
//    }

    //获取回文信息
    private boolean[][] getMat(String s) {
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        for(int i = n - 1; i >= 0; i--) {
            for(int j = i; j < n; j++) {
                if(i == j) {
                    dp[i][j] = true;
                } else if(i + 1 == j) {
                    dp[i][j] = s.charAt(i) == s.charAt(j);
                } else {
                    dp[i][j] = (dp[i + 1][j - 1]) && (s.charAt(i) == s.charAt(j));
                }
            }
        }
        return dp;
    }

//    public int minCut(String s) {
//        int len = s.length();
//        if(len == 0) {
//            return 0;
//        }
//        if(judge(s, 0, len - 1)) {
//            return 0;
//        }
//        int[] dp = new int[len + 1];
//        //初始化
//        //填充可以被分割的最大次数
//        for(int i = 1; i <= len; i++) {
//            dp[i] = i - 1;
//        }
//        boolean[][] mat = getMat(s);
//        for(int i = 2; i <= len; i++) {
//            if(judge(s, 0, i - 1)){//若前i个字符串整体回文
//                dp[i] = 0;
//                continue;
//            }
//            for(int j = 1; j < i; j++) {
//                if(mat[j][i - 1]) {//注意索引
//                    dp[i] = Math.min(dp[i], dp[j] + 1);
//                }
//            }
//        }
//        return dp[len];
//    }
//    //判断回文
//    private boolean judge(String s, int start, int end) {
//        while(start < end) {
//            if(s.charAt(start) == s.charAt(end)) {
//                start++;
//                end--;
//            } else {
//                break;
//            }
//        }
//        return start < end ? false : true;
//    }
}
